package com.leetcode.根据数据结构分类.数组;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: xiaomi
 * @date: 2021/1/14
 * @description: 1018. 可被 5 整除的二进制前缀
 * https://leetcode-cn.com/problems/binary-prefix-divisible-by-5/
 */
public class A_1018_可被5整除的二进制前缀 {

	/**
	 * 感觉只能通过位运算来优化除数的生成，对于求余运算没有优化的想法。
	 * --
	 * 需要考虑越界的情况！
	 * --
	 * 仔细想了一下，这道题其实并不是求余数，而是判断能否被整除
	 * 那就是需要判断二进制的后缀：5 的二进制 101
	 * 只要出现跟 101 重叠即可！
	 * FAIL!
	 * @param A
	 * @returnacacaca
	 */
	public List<Boolean> prefixesDivBy5(int[] A) {
		int len = A.length;
		List<Boolean> res = new ArrayList<>(len);
		int temp = 0;
		for (int i = 0; i < len; i++) {
			temp = (temp << 1) + A[i];
			res.add(temp % 5 == 0);
		}
		return res;
	}


	/**
	 * 基于上面的考虑实现的位运算解法
	 * 101
	 * --
	 * 好吧，不能通过位运算实现！
	 * 只能通过将余数计算！
	 * 7=5+2
	 * 14=5*2+2*2
	 * FAIL!
	 * @param A
	 * @return
	 */
	public List<Boolean> prefixesDivBy5ByBitwise(int[] A) {
		int len = A.length;
		List<Boolean> res = new ArrayList<>(len);

		if (len > 2) {
			for (int i = 0; i < 2; i++) {
				if (A[i] == 0) {
					res.add(true);
				} else {
					res.add(false);
				}
			}
		} else {
			for (int i = 0; i < len; i++) {
				if (A[i] == 0) {
					res.add(true);
				} else {
					res.add(false);
				}
			}
		}

		//预先判断头部
		int end = 2;


		//一个滑动窗口
		for (int i = end; i < len; i++) {
			if ((A[end] == 0 && A[end - 1] == 0 && A[end - 2] == 0) ||
					(A[end] == 1 && A[end - 1] == 0 && A[end - 2] == 1)) {
				res.add(true);
			} else {
				res.add(false);
			}
		}
		return res;
	}

	/**
	 * 通过余数实现
	 *
	 * @param A
	 * @return
	 */
	public List<Boolean> prefixesDivBy5ByRemainder(int[] A) {
		int len = A.length;
		List<Boolean> res = new ArrayList<>(len);
		int temp = 0;
		for (int i = 0; i < len; i++) {
			temp = ((temp << 1) + A[i]) % 5;
			res.add(temp == 0);
		}
		return res;
	}

}
